iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 6
1
自我挑戰組

神羅天征! 一起(爆肝)征服程式解題系列 第 6

[Day 6] LeetCode - 376 Wiggle Subsequence

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog: [解題] LeetCode - 376 Wiggle Subsequence

平台:

LeetCode

題號:

376 - Wiggle Subsequence

題目連結:

https://leetcode.com/problems/wiggle-subsequence/

題目說明:

        輸入一個數字序列,求有最長長度的擺動子序列(Wiggle Subsequence),並輸出此原始序列的長度。擺動序列的定義為原本序列是[a, b, c, d, .... x],而它們的相差序列[b - a, c - b, d - c, ...., x - w]裡的元素都是以正和負交替呈現。

  比如範例輸入的[1,7,4,9,2,5],相差序列為[6,-3,5,-7,3],符合擺動序列的規則,也是最長的擺動子序列,所以答案是6。

  但如果序列是[1, 2, 3, 4],最長的擺動子序列為[1]或[2]或[3],所以答案是2 ( [1, 2] 或 [1, 3] 或 [1, 4] 或 [2, 3] 或 [2, 4] 或 [3, 4] )。

解題方法:

  使用貪婪法,貪婪的原則為只要遇到轉折點,也就是下一個值變小或者下一個值變大,則代表符合擺動序列的長度就加1。

  像下方的狀態機,一開始在BEGIN的狀態,只要值一有變化,則進入到UP或DOWN的狀態。UP/DOWN狀態則持續比對目前的值和下一個值是否有變小/變大,有的話則長度加1。

  須注意edge case空值或只有1個元素的狀況。

難度為Medium

程式碼 (C++ 與 C#):

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2){
            return nums.size();
        }
        
        const int BEGIN = 0;
        const int UP = 1;
        const int DOWN = 2;
        int curState = BEGIN;
        int maxLength = 1;
        for(int i = 1;i < nums.size() ; ++i){
            switch(curState){
                case BEGIN:
                    if(nums[i-1] > nums[i]){
                        curState = DOWN;
                        maxLength++;
                    }
                    else if(nums[i-1] < nums[i]){
                        curState = UP;
                        maxLength++;
                    }
                    break;
                case UP:
                    if(nums[i-1] > nums[i]){
                        curState = DOWN;
                        maxLength++;
                    }
                    break;
                case DOWN:
                    if(nums[i-1] < nums[i]){
                        curState = UP;
                        maxLength++;
                    }
                    break;
            }
        }
        
        return maxLength;
    }
};

int main()
{
    Solution s;
	vector<int> nums{1,17,5,10,13,15,10,5,16,8}; 
    cout << s.wiggleMaxLength(nums) << endl;

    return 0;
}

using System;

namespace LeetCode376
{
    public class Solution {
        const int BEGIN = 0;
        const int UP = 1;
        const int DOWN = 2;
        public int WiggleMaxLength(int[] nums) {
            if(nums.Length < 2){
                return nums.Length;
            }
            
            int curState = BEGIN;
            int maxLength = 1;
            for(int i = 1;i < nums.Length ; ++i){
                switch(curState){
                    case BEGIN:
                        if(nums[i-1] > nums[i]){
                            curState = DOWN;
                            maxLength++;
                        }
                        else if(nums[i-1] < nums[i]){
                            curState = UP;
                            maxLength++;
                        }
                        break;
                    case UP:
                        if(nums[i-1] > nums[i]){
                            curState = DOWN;
                            maxLength++;
                        }
                        break;
                    case DOWN:
                        if(nums[i-1] < nums[i]){
                            curState = UP;
                            maxLength++;
                        }
                        break;
                }
            }
            
            return maxLength;
            
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[]{1,17,5,10,13,15,10,5,16,8};
            Console.WriteLine(new Solution().WiggleMaxLength(nums));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#):

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/300-399/376.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/300-399/376.cs


上一篇
[Day 5] LeetCode - 113 Path Sum II
下一篇
[Day 7] LeetCode - 1094 Car Pooling
系列文
神羅天征! 一起(爆肝)征服程式解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言